#pragma once

#include<vector>
using namespace std;


class UnionFindSet
{
public:
	UnionFindSet(size_t n)
	{
		_ufs.resize(n, -1);
	}

	size_t FindRoot(size_t x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}

		while (_ufs[x] >= 0)
		{
			size_t parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}

		return root;
	}

	void Union(size_t x, size_t y)
	{
		size_t root1 = FindRoot(x);
		size_t root2 = FindRoot(y);

		if (root1 == root2)
			return;

		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	bool InSet(size_t x, size_t y)
	{
		size_t root1 = FindRoot(x);
		size_t root2 = FindRoot(y);

		if (root1 == root2)
			return true;
		else
			return false;
	}
private:
	vector<int> _ufs;
};